class BinaryCodeTool:
    def __init__(self, length=0):
        # length仅用于输出
        self.length = length

    def subtract(self, ACode, BCode):
        """
        伪二进制数减法
        ACode和BCode是int(或其他整型),但是我把它们看成是二进制数
        要求实现:
        ACode某位为1,BCode相应位为0,则结果相应位为1
        ACode某位为1,BCode相应位为1,则结果相应位为0
        ACode某位为0,BCode相应位为0,则结果相应位为0
        ACode某位为0,BCode相应位为1,则结果相应位为0
        方法:
        (1)先将A和B异或,把A中为1而B中不为1的位“提取”出来,得到C
        (2)再将C与A进行"与"运算,从而将 那些A中为0而B中不为0 的位给去掉
        """
        C = ACode ^ BCode
        res = C & ACode
        return res

    def indexOfTrue(self, binCode):
        """
        返回为1的最低索引,最右边的位索引为0。若没有位是1,则返回-1
        """
        if binCode != 0:
            idx = 0
            while True:
                if self.test(binCode, idx):
                    return idx
                idx += 1
        else:
            return -1

    def setLength(self, length):
        self.length = length

    def getLength(self):
        return self.length

    def test(self, binCode, index):
        """index从0开始,从右往左"""
        return bool(binCode & (0b1 << index))

    def find(self, binCode, val):
        """最右边的位的索引是0
        返回val的最低索引,若没有val值,返回-1
        """
        assert val in [0, 1], "val是除0和1外的其他值"
        assert self.length > 0, "length <= 0"
        length = self.length
        val = True if val == 1 else False
        for i in range(length):
            if self.test(binCode, i) == val:
                return i
        return -1

    def all(self, binCode):
        """前提是定义好self.length"""
        # for i in range(self.length):
        #     if not self.test(binCode, i):
        #         return False
        # return True
        assert self.length > 0, "length <= 0, length={}".format(self.length)
        t = pow(2, self.length) - 1
        res = (t ^ binCode) & t
        return res == 0

    def any(self, binCode):
        """如果有一位是1,则返回True"""
        assert self.length > 0, "length <= 0"
        assert binCode >= 0, "binCode小于0"
        return binCode > 0

    def countVal(self, binCode, val):
        """有多少位是1"""
        assert val in [0, 1], "val是除0和1外的其他值"
        assert self.length > 0, "参数length<=0"
        val = True if val == 1 else False
        cnt = 0
        for idx in range(self.length):
            if self.test(binCode, idx) == val:
                cnt += 1
        return cnt

    def chgToTrue(self, binCode, index):
        return binCode | (0b1 << index)

    def chgToFalse(self, binCode, index):
        return binCode ^ (0b1 << index) if self.test(binCode, index) else binCode

    def chgToList(self, binCode):
        return [True if self.test(binCode, i) else False for i in range(self.length)]

    def dump(self, binCode, digit=0, useLength=False):
        # digits是自定义位数, useLength则依赖于之前设定的self.length
        assert not (digit != 0 and useLength), "自定义位数和使用预设的位数矛盾"
        assert digit >= 0, "自定义位数小于0"
        temp = bin(binCode)
        if digit > 0:
            strTemp = temp[:2] + temp[2:].zfill(digit)
        elif useLength:
            strTemp = temp[:2] + temp[2:].zfill(self.length)
        else:
            strTemp = temp
        print(strTemp)


class MovingParticle:
    """code=1时,左上右下型粒子"""
    """code=2时,左下右上型粒子"""
    __EAST = 1
    __STOP = 0

    def __init__(self, coord, des, walls, action=__EAST, code=1):
        self.__coord = coord
        self.__des = des
        self.__walls = walls
        self.__action = action
        self.__code = code

    def __check(self):
        assert self.__code in [1, 2], "__code是其他值"
        if self.__code == 1:
            return self.__coord[0] <= self.__des[0] and self.__coord[1] >= self.__des[1]
        elif self.__code == 2:
            return self.__coord[0] <= self.__des[0] and self.__coord[1] <= self.__des[1]

    def move(self, VisitedBitmap):
        sub = None
        if self.__action == self.__EAST:
            x = self.__coord[0]
            y = self.__coord[1]
            nexty = y - 1 if self.__code == 1 else y + 1
            if self.__walls[x + 1][y]:
                if not VisitedBitmap[x][nexty] and not self.__walls[x][nexty]:
                    self.__coord = (x, nexty)
                    VisitedBitmap[x][nexty] = True
                else:
                    # 证明这个死掉了
                    self.__action = self.__STOP
            else:
                self.__coord = (x + 1, y)
                if not self.__walls[x][nexty] and not VisitedBitmap[x][nexty]:
                    # 繁殖出一个子运动粒子
                    sub = MovingParticle((x, nexty), self.__des, self.__walls, self.__EAST, self.__code)
                    VisitedBitmap[x][nexty] = True
                    if not sub.__check():
                        sub = None
            if not self.__check():
                self.__action = self.__STOP
        return sub

    def output(self):
        if self.__coord == self.__des:
            return 1
        elif self.__action == self.__EAST:
            return 0
        elif self.__action == self.__STOP:
            return -1

    def dump(self):
        print("coord = {}, des = {}, code = {}, action={}, __EAST={}".format(
            self.__coord, self.__des, self.__code, self.__action, self.__EAST))
